   
    /* https://www.nowcoder.com/practice/1025ffc2939547e39e8a38a955de1dd3?tpId=46&tqId=29048&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
     * 回文串分割
     *O(N^3)
     * */
    public class Solution {
        public boolean isPalindromes(String s, int left, int right) {
            while (left <= right) {
                if (s.charAt(left) != s.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

        public int minCut(String s) {
            if (s.length() == 0) {
                return 0;
            }
            if (isPalindromes(s, 0, s.length() - 1)) {
                return 0;
            }
            int len = s.length();
            int[] array = new int[len + 1];
            for (int i = 1; i <= len; i++) {
                array[i] = i - 1;
            }
            //前i个字符需要多少次分割 F(i)
            for (int i = 2; i <= s.length(); i++) {
                if (isPalindromes(s, 0, i - 1)) {
                    array[i] = 0;
                    continue;
                }
                // j < i && [j+1,i]是回文串  F(i)=F(j)+1;
                //第j个字符，第i个字符
                for (int j = 1; j < i; j++) {
                    if (isPalindromes(s, j, i - 1)) {
                        array[i] = min(array[j] + 1, array[i]);
                    }
                }
            }
//        for (int i = 0; i <= len; i++) {
//            array[i] = i - 1;
//        }
//        for (int i = 2; i <= len; i++) {
//            for (int j = 0; j < i; j++) {
//                if(isPalindromes(s,j,i-1)){
//                    array[i] = min(array[i],array[j] + 1);
//                }
//            }
//        }
            return array[len];
        }
    }